package ru.tests.betterprogrammer;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * TODO: add description
 * Date: 12.08.11 22:13
 *
 * @author Alexander Troshanin
 */
public class Task3 {

    public static void main(String[] args) {
        NodeImpl c1 = new NodeImpl(2);
        NodeImpl c11 = new NodeImpl(2);
        NodeImpl c12 = new NodeImpl(3);
        NodeImpl c13 = new NodeImpl(4);

        NodeImpl c111 = new NodeImpl(5);
        NodeImpl c112 = new NodeImpl(6);
        NodeImpl c113 = new NodeImpl(7);

        NodeImpl c211 = new NodeImpl(8);
        NodeImpl c212 = new NodeImpl(9);
        NodeImpl c213 = new NodeImpl(10);

        NodeImpl c311 = new NodeImpl(11);
        NodeImpl c312 = new NodeImpl(12);
        NodeImpl c313 = new NodeImpl(13);
        List<Node> childs1 = new ArrayList<Node>();
        childs1.add(c11);
        childs1.add(c12);
        childs1.add(c13);

        c1.setChilds(childs1);

        List<Node> childs11 = new ArrayList<Node>();
        childs11.add(c111);
        childs11.add(c112);
        childs11.add(c113);
        c11.setChilds(childs11);

        List<Node> childs12 = new ArrayList<Node>();
        childs12.add(c211);
        childs12.add(c212);
        childs12.add(c213);
        c12.setChilds(childs12);

        List<Node> childs13 = new ArrayList<Node>();
        childs13.add(c311);
        childs13.add(c312);
        childs13.add(c313);
        c13.setChilds(childs13);

        ;

        System.out.println(getAverage(c1));

    }

    // Please do not change this interface
    public static interface Node {
        int getValue();

        List<Node> getChildren();
    }

    public static class NodeImpl implements Node {

        int v;

        List<Node> childs;

        public NodeImpl(int v) {
            this.v = v;
        }

        @Override
        public int getValue() {
            return v;
        }

        @Override
        public List<Node> getChildren() {
            return childs;
        }

        public void setChilds(List<Node> childs) {
            this.childs = childs;
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder();
            sb.append("NodeImpl");
            sb.append("{v=").append(v);
            sb.append('}');
            return sb.toString();
        }
    }

    public static double getAverage(Node root) {
        /*
          Please implement this method to
          return the average of all node values (Node.getValue()) in the tree.
         */
        StackNode stack = new StackNode(root.getChildren().iterator());
        long result = root.getValue();
        int nodesCnt = 1;
        do {

            if (stack.value.hasNext()) {
                Node nextChild = stack.value.next();
                result += nextChild.getValue();
                nodesCnt++;
                if (nextChild.getChildren() != null && !nextChild.getChildren().isEmpty()) {
                    StackNode nextStack = new StackNode(nextChild.getChildren().iterator());
                    stack.next = nextStack;
                    nextStack.prev = stack;
                    stack = nextStack;
                }
            } else {
                stack = stack.prev;
            }

        } while (stack != null);

        return ((double )result) / nodesCnt;
    }


    static class StackNode {
        Iterator<Node> value;
        StackNode next;
        StackNode prev;

        StackNode(Iterator<Node> value) {
            this.value = value;
        }

    }


}
